#include "KamaCoder.h"
using namespace std;

const int MAXINT16 = 32767;

int KamaCoder47::run() {
  // 输入
  int n, m, s, t, val;
  cin >> n >> m;  // n为节点数，m为边的个数
  vector<vector<int>> graph(n + 1, vector<int>(n + 1, MAXINT16));  // 图的邻接表
  for (int i = 0; i < m; i++) {
    cin >> s >> t >> val;  // 输入有向边、权值
    graph[s][t] = val;
  }
  int start = 1;  // 起点为1
  int end = n;    // 终点

  // 创建minDist数组
  vector<int> minDist(n + 1, MAXINT16);
  minDist[start] = 0;
  // 创建记录访问数组
  vector<int> visited(n + 1, false);

  // 遍历所有节点
  int sum = n;
  while (sum--) {           // 最多访问n-1条边
    int minVal = MAXINT16;  // 最小距离
    int cur = 1;
    // 确定当前节点
    for (int j = 1; j <= n; j++) {
      // 该节点没有加入最小生成树中，并且距离最小
      if (!visited[j] && minVal > minDist[j]) {
        minVal = minDist[j];
        cur = j;
      }
    }
    // 标记该节点已经访问过
    visited[cur] = true;

    // 更新最小距离数组
    for (int v = 1; v <= n; v++) {
      // grid[cur][v]!=MAXINT16 表示不可抵达
      if (!visited[v] && graph[cur][v] != MAXINT16 &&
          minDist[cur] + graph[cur][v] <
              minDist[v]) {  // 当前节点+到新的节点的距离 小于
                             // minDist中新节点的距离
        minDist[v] = minDist[cur] + graph[cur][v];
      }
    }
  }

  if (minDist[end] == MAXINT16)
    cout << -1 << endl;  // 终点不可抵达
  else {
    cout << minDist[end] << endl;  // 抵达终点的最小距离
  }

  return 0;
}

int KamaCoder47::run2() {
  // 输入
  int n, m, s, t, val;
  cin >> n >> m;

  // 图的邻接表
  vector<list<Edge>> graph(n + 1);

  // 输入有向边、权值
  for (int i = 0; i < m; i++) {
    cin >> s >> t >> val;
    // s->t 权值为val
    graph[s].push_back({t, val});
  }

  // 起点为1
  int start = 1;
  // 终点为n
  int end = n;

  // 创建minDist数组
  vector<int> minDist(n + 1, MAXINT16);
  minDist[start] = 0;

  // 创建记录访问数组
  vector<bool> visited(n + 1, false);

  // 初始化优先队列
  pq.push(pair<int, int>(start, 0));

  while (!pq.empty()) {
    // 取出节点对 <节点，距离>
    pair<int, int> cur = pq.top();
    pq.pop();

    if (visited[cur.first]) continue;  // 该节点已经访问过

    // 标记该节点已经访问过
    visited[cur.first] = true;

    // 更新最小距离数组
    for (Edge edge : graph[cur.first]) {  // 遍历该节点的邻接边
      // cur指向的节点edge.to , 边的权值edge.val
      if (!visited[edge.to] &&
          minDist[cur.first] + edge.val < minDist[edge.to]) {
        // 更新minDist[edge.to]
        minDist[edge.to] = minDist[cur.first] + edge.val;
        // 加入优先队列
        pq.push(pair<int, int>(edge.to, minDist[edge.to]));
      }
    }
  }

  if (minDist[end] == MAXINT16)
    cout << -1 << endl;  // 终点不可抵达
  else {
    cout << minDist[end] << endl;  // 抵达终点的最小距离
  }

  return 0;
}
